{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reordered Power of 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #counting #enumeration #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #计数 #枚举 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reorderedPowerOf2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重新排序得到 2 的幂"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定正整数&nbsp;<code>n</code>&nbsp;，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。</p>\n",
    "\n",
    "<p>如果我们可以通过上述方式得到&nbsp;2 的幂，返回 <code>true</code>；否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reordered-power-of-2](https://leetcode.cn/problems/reordered-power-of-2/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reordered-power-of-2](https://leetcode.cn/problems/reordered-power-of-2/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        answers = ['1', '2', '4', '8', '16', '23', '46', '128', '256', '125', '0124', '0248', '0469', '1289', '13468', '23678', '35566', '011237', '122446', '224588', '0145678', '0122579', '0134449', '0368888', '11266777', '23334455', '01466788', '112234778', '234455668', '012356789', '0112344778']\n",
    "        ns = str(n)\n",
    "        ai = [int(j) for j in ns]\n",
    "        ai.sort()\n",
    "        rs = ''\n",
    "        for j in ai:\n",
    "            rs = rs + str(j)\n",
    "        \n",
    "        return rs in answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        res = []\n",
    "        for i in range(31):\n",
    "            co = Counter(str(2**i))\n",
    "            res.append(co)\n",
    "        ans = Counter(str(n))\n",
    "        for i in res:\n",
    "            if i==ans:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        # m = 0\n",
    "        # for i in range(100):\n",
    "        #     if 2**i >= 10**9:\n",
    "        #         m = i\n",
    "        #         break\n",
    "        # nums = [2**i for i in range(m+2)]\n",
    "        # n1 = sorted(str(n))\n",
    "        # for item in nums:\n",
    "        #     if sorted(str(item)) == n1:\n",
    "        #         return True\n",
    "        # return False\n",
    "\n",
    "        tem = sorted(str(n))\n",
    "        ve = []\n",
    "        x =1\n",
    "        while x < 10**9:\n",
    "            ve.append(str(x))\n",
    "            x = x*2\n",
    "        for item in ve:\n",
    "            if sorted(str(item)) == tem:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        nstr=sorted(str(n))\n",
    "        x=1\n",
    "        while x<=2**31:\n",
    "            if sorted(str(x))==nstr:\n",
    "                return True\n",
    "            x<<=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        arr = [\n",
    "            '1',\n",
    "            '2',\n",
    "            '4',\n",
    "            '8',\n",
    "            '16',\n",
    "            '32',\n",
    "            '64',\n",
    "            '128',\n",
    "            '256',\n",
    "            '512',\n",
    "            '1024',\n",
    "            '2048',\n",
    "            '4096',\n",
    "            '8192',\n",
    "            '16384',\n",
    "            '32768',\n",
    "            '65536',\n",
    "            '131072',\n",
    "            '262144',\n",
    "            '524288',\n",
    "            '1048576',\n",
    "            '2097152',\n",
    "            '4194304',\n",
    "            '8388608',\n",
    "            '16777216',\n",
    "            '33554432',\n",
    "            '67108864',\n",
    "            '134217728',\n",
    "            '268435456',\n",
    "            '536870912',\n",
    "            '1073741824',\n",
    "        ]\n",
    "        arr_2 = []\n",
    "        arr_3 = [0]*10\n",
    "        length = len(str(n))\n",
    "        for i in arr:\n",
    "            if len(i) == length:\n",
    "                arr_2.append(i)\n",
    "        for c in str(n):\n",
    "            arr_3[int(c)] += 1\n",
    "        for i in arr_2:\n",
    "            found = True\n",
    "            arr_4 = [0]*10\n",
    "            for c in str(i):\n",
    "                arr_4[int(c)] += 1\n",
    "            for j in range(10):\n",
    "                if arr_4[j] != arr_3[j]:\n",
    "                    found = False\n",
    "                    break\n",
    "            if found:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#import itertools\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        return sorted(str(n)) in [sorted(str(1 << i)) for i in range(31)]\n",
    "\n",
    "        '''permutations = list(itertools.permutations(str(n)))\n",
    "        for p in permutations:\n",
    "            if p[0] == '0':\n",
    "                continue\n",
    "            x = int(''.join(list(p)))\n",
    "            while 1:\n",
    "                if x == 1:\n",
    "                    return True\n",
    "                if x % 2 != 0:\n",
    "                    break\n",
    "                x /= 2\n",
    "        return False'''\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        a = [2 ** i for i in range(32)]\n",
    "        b = sorted(str(n))\n",
    "        for i in a:\n",
    "            if sorted(str(i)) == b:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def countDigits(n: int) -> Tuple[int]:\n",
    "    cnt = [0] * 10\n",
    "    while n:\n",
    "        cnt[n % 10] += 1\n",
    "        n //= 10\n",
    "    return tuple(cnt)\n",
    "\n",
    "powerOf2Digits = {countDigits(1 << i) for i in range(30)}\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        return countDigits(n) in powerOf2Digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        nums,x=[],1\n",
    "        while x<=10**9:\n",
    "            temp=list(str(x))\n",
    "            temp.sort()\n",
    "            nums.append(tuple(temp))\n",
    "            x*=2\n",
    "        y=list(str(n))\n",
    "        y.sort()\n",
    "        if tuple(y) in nums:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        target = sorted(str(n))\n",
    "        for i in range(30):\n",
    "            if sorted(str(1 << i)) == target:\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        p=1\n",
    "        s=sorted(str(n))\n",
    "        while p<10**9:\n",
    "            if sorted(str(p))==s:\n",
    "                return True\n",
    "            p*=2\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        v = 1\r\n",
    "        s = set(['1'])\r\n",
    "        while(v <= 10 ** 9):\r\n",
    "            v *= 2\r\n",
    "            c = str(v)\r\n",
    "            lis = list(c)\r\n",
    "            lis.sort()\r\n",
    "            s.add(\"\".join(lis))\r\n",
    "\r\n",
    "        lis = list(str(n))\r\n",
    "        lis.sort()\r\n",
    "        c = \"\".join(lis)\r\n",
    "        return(c in s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        m = 0\n",
    "        for i in range(100):\n",
    "            if 2**i >= 10**9:\n",
    "                m = i\n",
    "                break\n",
    "        nums = [2**i for i in range(m+2)]\n",
    "        n1 = sorted(str(n))\n",
    "        for item in nums:\n",
    "            if sorted(str(item)) == n1:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def check(num):\n",
    "            numList = [0] * 10\n",
    "            while num:\n",
    "                numList[num % 10] += 1\n",
    "                num //= 10\n",
    "            return numList\n",
    "\n",
    "        pattern = check(n)\n",
    "        cnt = len(str(n))\n",
    "        k = 0\n",
    "        while len(str(1 << k)) <= cnt:\n",
    "            if len(str(1 << k)) == cnt:\n",
    "                if check(1 << k) == pattern:\n",
    "                    return True\n",
    "            k += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        v = 1\r\n",
    "        s = set(['1'])\r\n",
    "        while(v <= 10 ** 9):\r\n",
    "            v *= 2\r\n",
    "            c = str(v)\r\n",
    "            lis = list(c)\r\n",
    "            lis.sort()\r\n",
    "            s.add(\"\".join(lis))\r\n",
    "\r\n",
    "        lis = list(str(n))\r\n",
    "        lis.sort()\r\n",
    "        c = \"\".join(lis)\r\n",
    "        return(c in s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        s=sorted(str(n))\r\n",
    "        l=len(s)\r\n",
    "        Min=10**(l-1)\r\n",
    "        Max=10**l\r\n",
    "        x=1\r\n",
    "        while x<Min:\r\n",
    "            x<<=1\r\n",
    "        while x<Max:\r\n",
    "            if sorted(str(x))==s:\r\n",
    "                return True\r\n",
    "            x<<=1\r\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        l = list(str(n))\n",
    "        # while n !=0:\n",
    "        #     n,t = divmod(n,10)\n",
    "        #     l.append(t)\n",
    "        for i in permutations(l):\n",
    "            i = list(i)\n",
    "            if i and i[0]=='0':\n",
    "                continue\n",
    "            x = int(\"\".join(i))\n",
    "            if x & x-1 ==0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        v = 1\r\n",
    "        s = set(['1'])\r\n",
    "        while(v <= 10 ** 9):\r\n",
    "            v *= 2\r\n",
    "            s.add(\"\".join(sorted(str(v))))\r\n",
    "\r\n",
    "        c = \"\".join(sorted(str(n)))\r\n",
    "        return(c in s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        a = []\n",
    "        \n",
    "        i = 0\n",
    "        while i <= 30:\n",
    "            a.append(pow(2, i))\n",
    "            i += 1\n",
    "        \n",
    "        s = []\n",
    "        for x in a:\n",
    "            x = str(x)\n",
    "            s.append(''.join(map(str, sorted(map(int, x)))))\n",
    "        \n",
    "        n = str(n)\n",
    "        sn = ''.join(map(str, sorted(map(int, n))))\n",
    "        \n",
    "        for x in s:\n",
    "            if x == sn:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        v = 1\r\n",
    "        s = set(['1'])\r\n",
    "        while(v <= 10 ** 9):\r\n",
    "            v *= 2\r\n",
    "            c = str(v)\r\n",
    "            lis = list(c)\r\n",
    "            lis.sort()\r\n",
    "            s.add(\"\".join(lis))\r\n",
    "\r\n",
    "        lis = list(str(n))\r\n",
    "        lis.sort()\r\n",
    "        c = \"\".join(lis)\r\n",
    "        return(c in s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        mi = [str(2**i) for i in range(30)]\n",
    "        s_n = str(n)\n",
    "        for num in mi:\n",
    "            if len(s_n)==len(num):\n",
    "                s1 = list(s_n)\n",
    "                s2 = list(num)\n",
    "                s1 = sorted(s1)\n",
    "                s2 = sorted(s2)\n",
    "                if s1==s2:\n",
    "                    return  True\n",
    "            elif len(s_n)<len(num):\n",
    "                break\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cmp_to_key\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        self.preproc(9)\n",
    "        nstr = self.int_to_lst(n)\n",
    "        return nstr in self.dict_pow.keys()\n",
    "\n",
    "    dict_pow = {}\n",
    "\n",
    "    def preproc(self, maxlen: int):\n",
    "        if len(self.dict_pow.keys()) >= 1:\n",
    "            return\n",
    "        a = 1\n",
    "        while len(str(a)) <= maxlen:\n",
    "            self.dict_pow[self.int_to_lst(a)] = True\n",
    "            a *= 2\n",
    "\n",
    "    def int_to_lst(self, x: int):\n",
    "        a = x; ans = [\"0\" for i in range(10)]\n",
    "        while a > 0:\n",
    "            ans[a % 10] = str(int(ans[a % 10]) + 1)\n",
    "            a //= 10\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def cnt(num):\n",
    "            idx = [0] * 10\n",
    "            while num != 0:\n",
    "                idx[num%10] +=1\n",
    "                num = num // 10\n",
    "            return tuple(idx)\n",
    "        \n",
    "        hash_table = [cnt(2**i) for i in range(30)]\n",
    "        return cnt(n) in hash_table\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "def _get_cnts(n: int) -> Tuple[int]:\n",
    "    s = str(n)\n",
    "    cnts = Counter(s)\n",
    "    return tuple(cnts[str(i)] for i in range(10))\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        nums = [1 << i for i in range(31)]\n",
    "        all_cnts = {_get_cnts(x) for x in nums}\n",
    "        # print(all_cnts)\n",
    "        # print(_get_cnts(n))\n",
    "        return _get_cnts(n) in all_cnts\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def gen():\n",
    "            for i in range(30):\n",
    "                yield sorted(list(str(2**i)))\n",
    "        \n",
    "        g=gen()\n",
    "        return sorted(list(str(n))) in g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def countnumber(n: int) -> list[int]:\n",
    "    cnt = [0] * 10\n",
    "    while n:\n",
    "        cnt[n % 10] += 1\n",
    "        n //= 10\n",
    "    return cnt\n",
    "\n",
    "\n",
    "a = [countnumber(1 << i) for i in range(30)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        return countnumber(n) in a\n",
    "sw = Solution()\n",
    "print(sw.reorderedPowerOf2(10))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        #共30个数\n",
    "        lis=[]\n",
    "        num=1\n",
    "        \n",
    "        for i in range(30):\n",
    "            lis.append(Counter(str(num)))\n",
    "            num*=2\n",
    "        return Counter(str(n)) in lis\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        D=[int(i) for i in str(n)]\n",
    "        for i in range(n):\n",
    "            d=[int(i) for i in str(2**i)]\n",
    "            count=0\n",
    "            for j in range(10):\n",
    "                if D.count(j)==d.count(j):\n",
    "                    count+=1\n",
    "            if count==10:\n",
    "                \n",
    "                return True\n",
    "                break\n",
    "            if 2**i>10*n:\n",
    "                break\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        return sorted(str(n)) in map(lambda i : sorted(str(1 << i)), range(30))\n",
    "\n",
    "# 作者：_G_\n",
    "# 链接：https://leetcode.cn/problems/reordered-power-of-2/solutions/2430643/mei-ju-zi-fu-chuan-pi-pei-pythonyi-xing-qkvi1/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def countd(n):\n",
    "            cnt = [0] * 10\n",
    "            while n:\n",
    "                cnt[n % 10] += 1\n",
    "                n = n // 10\n",
    "            return tuple(cnt)\n",
    "\n",
    "        all = {countd(1 << i) for i in range(30)}\n",
    "\n",
    "        return countd(n) in all\n",
    "\n",
    "    def reorderedPowerOf22(self, n: int) -> bool:\n",
    "        l = len(str(n))\n",
    "        if l == 1:\n",
    "            return n == 1 or n == 2 or n == 4 or n == 8\n",
    "\n",
    "        s = set()\n",
    "        i = 1\n",
    "        while i <= 1e9:\n",
    "            s.add(i)\n",
    "            i = i << 1\n",
    "\n",
    "        if n in s:\n",
    "            return True\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        for c in str(n):\n",
    "            d[ord(c) - ord(\"0\")] += 1\n",
    "\n",
    "        if not (2 in d or 4 in d or 6 in d or 8 in d):\n",
    "            return False\n",
    "\n",
    "        def selectLast():\n",
    "            for n in d.keys():\n",
    "                if (n == 2 or n == 4 or n == 6 or n == 8) and d[n] > 0:\n",
    "                    d[n] -= 1\n",
    "                    if selectFirst(n):\n",
    "                        return True\n",
    "                    d[n] += 1\n",
    "            return False\n",
    "\n",
    "        def selectFirst(last):\n",
    "            for n in d.keys():\n",
    "                if n > 0 and d[n] > 0:\n",
    "                    d[n] -= 1\n",
    "                    if select(n * (10 ** (l - 1)), last, 1, 0):\n",
    "                        return True\n",
    "                    d[n] += 1\n",
    "            return False\n",
    "\n",
    "        def select(first, last, index, value):\n",
    "            if index == l - 1:\n",
    "                return first + value * 10 + last in s\n",
    "\n",
    "            for n in d.keys():\n",
    "                if d[n] > 0:\n",
    "                    d[n] -= 1\n",
    "                    if select(first, last, index + 1, value * 10 + n):\n",
    "                        return True\n",
    "                    d[n] += 1\n",
    "            return False\n",
    "\n",
    "        return selectLast()\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert Solution().reorderedPowerOf2(1)\n",
    "    # assert Solution().reorderedPowerOf2(2)\n",
    "    # assert not Solution().reorderedPowerOf2(5)\n",
    "    # assert not Solution().reorderedPowerOf2(10)\n",
    "    # assert Solution().reorderedPowerOf2(16)\n",
    "    # assert not Solution().reorderedPowerOf2(18)\n",
    "    # assert Solution().reorderedPowerOf2(64)\n",
    "    # assert not Solution().reorderedPowerOf2(65)\n",
    "    # assert Solution().reorderedPowerOf2(46)\n",
    "    # assert Solution().reorderedPowerOf2(1024)\n",
    "    # assert Solution().reorderedPowerOf2(218)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mask=[Counter(str(0))]\r\n",
    "tmp=1\r\n",
    "while tmp<10**9:\r\n",
    "    mask.append(Counter(str(tmp)))\r\n",
    "    tmp*=2\r\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        if Counter(str(n)) in mask:\r\n",
    "            return True\r\n",
    "        else:\r\n",
    "            return False\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        target = Counter(str(n))\n",
    "        for i in range(30):\n",
    "            if Counter(str(1 << i)) == target:\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ss=set()\n",
    "i=1\n",
    "while i<=1000000000:\n",
    "    ss.add(i)\n",
    "    i*=2\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        s=str(n)\n",
    "        length=len(s)\n",
    "        cnt=[0]*10\n",
    "        for c in s:\n",
    "            cnt[ord(c)-ord('0')]+=1\n",
    "        ans=False\n",
    "        def dfs(sb,cnt,i):\n",
    "            nonlocal ans\n",
    "            if i==length:\n",
    "                if int(sb) in ss and sb[0]!='0':\n",
    "                    ans=True\n",
    "                return\n",
    "            for k in range(10):\n",
    "                if cnt[k]>0:\n",
    "                    cnt[k]-=1\n",
    "                    dfs(sb+str(k),cnt,i+1)\n",
    "                    cnt[k]+=1\n",
    "            return\n",
    "        dfs(\"\",cnt,0)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "CNTofPower2 = [Counter(str(1 << i)) for i in range(30)]\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        cnt = Counter(str(n))\n",
    "        if cnt in CNTofPower2:\n",
    "            return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        #共30个数\n",
    "        lis=[]\n",
    "        num=1\n",
    "        test=Counter(str(n))\n",
    "        for i in range(30):\n",
    "            temp=Counter(str(num))\n",
    "            if test==temp: return True\n",
    "            num*=2\n",
    "        return Counter(str(n)) in lis\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "BASE = 1\n",
    "POW2 = []\n",
    "for _ in range(31):\n",
    "    POW2.append(BASE)\n",
    "    BASE *= 2\n",
    "CNTofPower2 = [Counter(str(x)) for x in POW2]\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        cnt = Counter(str(n))\n",
    "        if cnt in CNTofPower2:\n",
    "            return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "NUMS = set(str(sorted(str(1<<i))) for i in range(30))\n",
    "\n",
    "class Solution: \n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        return str(sorted(str(n))) in NUMS\n",
    "\n",
    "# 作者：Benhao\n",
    "# 链接：https://leetcode.cn/problems/reordered-power-of-2/solutions/1070375/pythonjavajavascript-gei-ni-liang-ge-zi-s7c1c/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        num2 = [2**i for i in range(31)]\n",
    "        chaxun = []\n",
    "        nums = [0]*10\n",
    "        while n>0:\n",
    "            shu = n%10\n",
    "            nums[shu]+=1\n",
    "            n = n//10\n",
    "        for i in range(len(num2)):\n",
    "            tt = [0]*10\n",
    "            num = num2[i]\n",
    "            while num>0:\n",
    "                shu = num%10\n",
    "                tt[shu]+=1\n",
    "                num = num//10\n",
    "            do = True\n",
    "            for j in range(10):\n",
    "                if nums[j]!=tt[j]:\n",
    "                    do = False\n",
    "                    break\n",
    "            if do :\n",
    "                return True\n",
    "\n",
    "\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        hash_map = []\n",
    "        for i in range(0, 30):\n",
    "            hash_map.append(sorted(str(2**i)))\n",
    "\n",
    "        return sorted(str(n)) in hash_map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        v = 1\r\n",
    "        s = set(['1'])\r\n",
    "        while(v <= 10 ** 9):\r\n",
    "            v *= 2\r\n",
    "            c = str(v)\r\n",
    "            lis = list(c)\r\n",
    "            lis.sort()\r\n",
    "            s.add(\"\".join(lis))\r\n",
    "        \r\n",
    "        lis = list(str(n))\r\n",
    "        lis.sort()\r\n",
    "        c = \"\".join(lis)\r\n",
    "        return(c in s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def get_dig( num:int ):\n",
    "            res_dig = 0\n",
    "            num_list = []\n",
    "            while num > 0:\n",
    "                res_dig += 1\n",
    "                num_list.append( num%10)\n",
    "                num //= 10\n",
    "            return res_dig, num_list\n",
    "        n_dig, n_list = get_dig(n)\n",
    "        n_list.sort()\n",
    "        pow_2 = 1\n",
    "        while True:\n",
    "            tmp_dig , tmp_list = get_dig( pow_2 )\n",
    "            if tmp_dig < n_dig:\n",
    "                pow_2*=2\n",
    "            elif tmp_dig == n_dig:\n",
    "                tmp_list.sort()\n",
    "                if tmp_list == n_list:\n",
    "                    return True\n",
    "                else:\n",
    "                    pow_2 *=2\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "nums = set()\n",
    "l = 0\n",
    "while 2 ** l <= 10 ** 9:\n",
    "    nums.add(2 ** l)\n",
    "    l += 1\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        if n in nums: return True\n",
    "        \n",
    "        # 如果n不在，就判断是否存在一个数和n是字母异位词\n",
    "        def check(a, b):\n",
    "            a = str(a)\n",
    "            b = str(b)\n",
    "            return sorted(a) == sorted(b)\n",
    "\n",
    "        for num in nums:\n",
    "            if check(n, num): return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        v = 1\r\n",
    "        s = set(['1'])\r\n",
    "        while(v <= 10 ** 9):\r\n",
    "            v *= 2\r\n",
    "            c = str(v)\r\n",
    "            s.add(\"\".join(sorted(c)))\r\n",
    "\r\n",
    "        c = \"\".join(sorted(str(n)))\r\n",
    "        return(c in s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isPowerOfTwo(n):\n",
    "    return n&(n-1)==0#2的幂具有以下性质 n&n-1==0 \n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        nums=sorted(list(str(n)))\n",
    "        m=len(nums)\n",
    "        vis=[False]*m\n",
    "\n",
    "        def backtracking(idx,num):\n",
    "            if idx==m:\n",
    "                return isPowerOfTwo(num)\n",
    "            \n",
    "            for i,ch in enumerate(nums):\n",
    "                #不能含有前导0\n",
    "                #第二个数处理同一树枝上下标索引相同的元素\n",
    "                #第三个是处理在全排列问题时候值相同  因为nums已经排好序  所以这是在处理同一树层含有相同元素 避免出现重复元素\n",
    "                if (num == 0 and ch == '0') or vis[i] or (i > 0 and not vis[i - 1] and ch == nums[i - 1]):\n",
    "                    continue\n",
    "                vis[i]=True\n",
    "                if backtracking(idx+1,num*10+ord(ch) - ord('0')):\n",
    "                    return True\n",
    "                vis[i]=False\n",
    "            return False\n",
    "        return backtracking(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        i = 0\n",
    "        length = defaultdict(list)\n",
    "        while 2 ** i <= 10**9:\n",
    "            x= list(str(2 ** i))\n",
    "            x.sort()\n",
    "            length[len(str(2 ** i))].append(x)\n",
    "            i += 1\n",
    "        nums = list(str(n))\n",
    "        nums.sort()\n",
    "        return True if nums in length[len(nums)] else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        goal = ''.join(sorted(ch for ch in str(n)))\n",
    "        pool = [1]\n",
    "        while pool[-1] < 10**9:\n",
    "            pool.append(pool[-1] * 2)\n",
    "        for num in pool:\n",
    "            if ''.join(sorted(ch for ch in str(num))) == goal:\n",
    "                return True\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        s = str(n)\n",
    "        hashmap = [True]*len(s)\n",
    "        def dfs(idx,num):\n",
    "            if idx == len(s)+1:\n",
    "                return num&(num-1) == 0\n",
    "            for i in range(len(s)):\n",
    "                if not hashmap[i]:\n",
    "                    continue\n",
    "                if idx == 1 and s[i] == '0':\n",
    "                    continue\n",
    "                hashmap[i] = False\n",
    "                if dfs(idx+1,num*10+int(s[i])):\n",
    "                    return True\n",
    "                hashmap[i] = True\n",
    "            return False\n",
    "        return dfs(1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mask=[Counter(str(0))]\r\n",
    "tmp=1\r\n",
    "while tmp<10**9:\r\n",
    "    mask.append(Counter(str(tmp)))\r\n",
    "    tmp<<=1\r\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        if Counter(str(n)) in mask:\r\n",
    "            return True\r\n",
    "        else:\r\n",
    "            return False\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\r\n",
    "        v = 1\r\n",
    "        s = set(['1'])\r\n",
    "        while(v <= 10 ** 9):\r\n",
    "            v *= 2\r\n",
    "            c = str(v)\r\n",
    "            lis = list(c)\r\n",
    "            lis.sort()\r\n",
    "            s.add(\"\".join(lis))\r\n",
    "        \r\n",
    "        lis = list(str(n))\r\n",
    "        lis.sort()\r\n",
    "        c = \"\".join(lis)\r\n",
    "        return(c in s)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def finger(n:int)->str:\n",
    "    return ''.join(sorted(str(n)))\n",
    "\n",
    "st = set()\n",
    "n=1\n",
    "while n<=10**9:\n",
    "    st.add(finger(n))\n",
    "    n*=2\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        return finger(n) in st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def check(num):\n",
    "            numList = [0] * 10\n",
    "            while num:\n",
    "                numList[num % 10] += 1\n",
    "                num //= 10\n",
    "            return numList\n",
    "\n",
    "        pattern = check(n)\n",
    "        cnt = len(str(n))\n",
    "        k = 0\n",
    "        while len(str(1 << k)) <= cnt:\n",
    "            if len(str(1 << k)) == cnt:\n",
    "                if check(1 << k) == pattern:\n",
    "                    return True\n",
    "            k += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        digits = [c for c in str(n)]\n",
    "        n = len(digits)\n",
    "        selected = []\n",
    "        visited = [False] * n\n",
    "        result = False\n",
    "\n",
    "        def dfs():\n",
    "            nonlocal result  # 声明result为非局部变量\n",
    "            if len(selected) == len(digits):\n",
    "                if bin(int(''.join(selected)))[2:].count('1') == 1:\n",
    "                    result = True\n",
    "                return\n",
    "            if result:\n",
    "                return\n",
    "            for i, digit in enumerate(digits):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                if digit == '0' and not selected:\n",
    "                    continue\n",
    "                selected.append(digit)\n",
    "                visited[i] = True\n",
    "                dfs()\n",
    "                visited[i] = False\n",
    "                selected.pop()\n",
    "\n",
    "        dfs()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        two_mi = []\n",
    "        for i in range(100000):\n",
    "            if 2**i < 1000000000:\n",
    "                two_mi.append(2**i)\n",
    "            else:\n",
    "                break\n",
    "        two_mi_arr = []\n",
    "        for i in two_mi:\n",
    "            i = list(str(i))\n",
    "            i.sort()\n",
    "            two_mi_arr.append(i)\n",
    "        n = list(str(n))\n",
    "        n.sort()\n",
    "        if n in two_mi_arr:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        i = 0\n",
    "        q = []\n",
    "        while 2 ** i <= 1e9:\n",
    "            a = sorted(str(2 ** i))\n",
    "            q.append(a)\n",
    "            i += 1\n",
    "        b = sorted(str(n))\n",
    "        if b in q:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:        \n",
    "        w=[]\n",
    "        for i in range(34):\n",
    "            w.append(''.join(sorted(str(2**i))))\n",
    "        return ''.join(sorted(str(n))) in w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def check(num):\n",
    "            numList = [0] * 10\n",
    "            while num:\n",
    "                numList[num % 10] += 1\n",
    "                num //= 10\n",
    "            return numList\n",
    "\n",
    "        pattern = check(n)\n",
    "        cnt = len(str(n))\n",
    "        k = 0\n",
    "        while len(str(1 << k)) <= cnt:\n",
    "            if len(str(1 << k)) == cnt:\n",
    "                if check(1 << k) == pattern:\n",
    "                    return True\n",
    "            k += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def check(num):\n",
    "            return num & (num - 1) == 0\n",
    "        nums = sorted(list(str(n)))\n",
    "        visited = [False for _ in range(len(nums))]\n",
    "        def backtrack(li, ne):\n",
    "            if len(li) == len(nums):\n",
    "                return check(int(''.join(li)))\n",
    "            for i in range(len(ne)):\n",
    "                if (not li and ne[i] == '0') or (i > 0 and ne[i] == ne[i - 1]):\n",
    "                    continue\n",
    "                if backtrack(li + [ne[i]], ne[:i] + ne[i + 1:]):\n",
    "                    return True\n",
    "            return False\n",
    "        return backtrack([], nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def countDigits(n):\n",
    "    cnt=[0]*10\n",
    "    while n:\n",
    "        cnt[n%10]+=1\n",
    "        n//=10\n",
    "    return tuple(cnt)\n",
    "\n",
    "powerOf2Digits={countDigits(1<<i) for i in range(30)}\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        return countDigits(n) in powerOf2Digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        nums = list(str(n))\n",
    "\n",
    "        comb = permutations(nums, len(nums))\n",
    "\n",
    "        for num in comb:\n",
    "            if num[0] == '0':\n",
    "                continue\n",
    "            num = int(''.join(num))\n",
    "        \n",
    "            if (num & num-1) == 0:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def freq_nums(num):\n",
    "            freq = [0] * 10\n",
    "            while num:\n",
    "                left = num % 10\n",
    "                num //= 10\n",
    "                freq[left] += 1\n",
    "            \n",
    "            return tuple(freq)\n",
    "\n",
    "        \n",
    "        return freq_nums(n) in { freq_nums(1<<i) for i in range(30)}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        def check(num):\n",
    "            return num & (num - 1) == 0\n",
    "        nums = sorted(list(str(n)))\n",
    "        visited = [False for _ in range(len(nums))]\n",
    "        def backtrack(i, num):\n",
    "            if i == len(nums):\n",
    "                return check(num)\n",
    "            for j in range(len(nums)):\n",
    "                if (num == 0 and nums[j] == '0') or (visited[j]) or (j > 0 and not visited[j - 1] and nums[j] == nums[j - 1]):\n",
    "                    continue\n",
    "                visited[j] = True\n",
    "                if backtrack(i + 1, num * 10 + int(nums[j])):\n",
    "                    return True\n",
    "                visited[j] = False\n",
    "            return False\n",
    "        return backtrack(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isPowerOfTwo(n: int) -> bool:\n",
    "    return (n & (n - 1)) == 0\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        nums = sorted(list(str(n)))\n",
    "        m = len(nums)\n",
    "        vis = [False] * m\n",
    "\n",
    "        def backtrack(idx: int, num: int) -> bool:\n",
    "            if idx == m:\n",
    "                return isPowerOfTwo(num)\n",
    "            for i, ch in enumerate(nums):\n",
    "                # 不能有前导零\n",
    "                if (num == 0 and ch == '0') or vis[i] or (i > 0 and not vis[i - 1] and ch == nums[i - 1]):\n",
    "                    continue\n",
    "                vis[i] = True\n",
    "                if backtrack(idx + 1, num * 10 + ord(ch) - ord('0')):\n",
    "                    return True\n",
    "                vis[i] = False\n",
    "            return False\n",
    "\n",
    "        return backtrack(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(num):\n",
    "    while(num > 1):\n",
    "        if(num % 2 == 1):\n",
    "            return False\n",
    "        num = num // 2\n",
    "    return True\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.flag = False\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        nums = list(str(n))\n",
    "        nums.sort()\n",
    "        m = len(nums)\n",
    "        book = [0]*m\n",
    "        def backtracking(cnt):\n",
    "            if(cnt == m):\n",
    "                num = int(''.join(self.path[:]))\n",
    "                if(check(num)):\n",
    "                    self.flag = True\n",
    "                    return\n",
    "                return\n",
    "            if(self.flag):\n",
    "                return\n",
    "            for i in range(m):\n",
    "                if(i>0 and nums[i-1]==nums[i] and book[i-1]==0):\n",
    "                    continue\n",
    "                if(book[i] == 0 and len(self.path) == 0 and nums[i] == '0'):\n",
    "                    continue\n",
    "                if(book[i] == 0):\n",
    "                    book[i] = 1\n",
    "                    self.path.append(nums[i])\n",
    "                    backtracking(cnt+1)\n",
    "                    book[i] = 0\n",
    "                    self.path.pop()\n",
    "            return\n",
    "        backtracking(0)\n",
    "        return self.flag\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def countnumber(n: int) -> tuple[int]:\n",
    "    cnt = [0] * 10\n",
    "    while n:\n",
    "        cnt[n % 10] += 1\n",
    "        n //= 10\n",
    "    return tuple(cnt)\n",
    "\n",
    "\n",
    "a = {countnumber(1 << i) for i in range(30)}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        return countnumber(n) in a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorderedPowerOf2(self, n: int) -> bool:\n",
    "        num=list(str(n))\n",
    "        sign={}\n",
    "        for i in num:\n",
    "            if i not in sign:\n",
    "                sign[i]=1\n",
    "            else:\n",
    "                sign[i]+=1\n",
    "        for i in range(31):\n",
    "            sign1={}\n",
    "            temp=2**i\n",
    "            temp=list(str(temp))\n",
    "            for j in temp:\n",
    "                if j not in sign1:\n",
    "                    sign1[j]=1\n",
    "                else:\n",
    "                    sign1[j]+=1\n",
    "            if sign==sign1:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
